package com.major.dawn.leetCode.list;

public class DetectCycle {

//    由于是单向列表，所以判断是否存在环，需要最后一个节点的指向，如果是否环的话最后一个节点永远不会为空。怎么判断节点的元素是否重复很关键。
//    value没有办法判断唯一性，因为没有说明value不相等，只能通过ListNode对象来判断，所以可以指定。
//    1、维护HashMap<ListNode,Integer>  对象和索引下标 ，containKey return index   O(N)
//    2、不耗费空间，双指针探测，快慢指针，如果有环就必定会相遇；关键是判断相遇后的规律
    public ListNode detectCycle(ListNode head) {


        if (head == null) {
            return null;
        }

//        第一步   确认是否有环
        ListNode fast = head;
        ListNode slow = head;

        ListNode listNode = getListNode(fast, slow);
        if (listNode == null) {
            return null;
        }

        ListNode part1 = head;

        while (part1 != listNode) {
            part1 = part1.next;
            slow = slow.next;
        }

        return listNode;
    }

    private ListNode getListNode(ListNode fast, ListNode slow) {
        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return slow;
            }

        }
        return null;
    }


}
